רשימות מקושרות מול מערכים

מבנה נתונים ואלגוריתמים

שיקולי ביצועים

יישומים של אוסף נתונים המבוססים על מערך יפגינו לרוב ביצועים מעט יותר טובים מאשר אלו המבוססים על רשימה

מקושרת. ההבדל יהיה בסדר גודל של הגורם קבוע: סריקת מערכים ורשימות מקושרות דורשים בעיקרון O(n) פעולות.

עם זאת, הגורם הקבוע תורם להבדל הקטן בביצועים לטובת המערכים:

1. ניתן לחשב את הכתובת של האיבר הבא במערך כאשר ידוע לנו הכתובת הנוכחית וגודל האיבר - שני אלו

נשמרים באוגר.

כתובת הבאה = כתובת נוכחית + גודל

ניתן להשתמש בשתי הכתובות באוגר אחד. מאחר ולא נדרשת גישה לזיכרון, זוהי פעולה בת מחזור בודד של

מעבד RISC מודרני.

2. בשימוש במערך, המידע נשמר בהקצאת זיכרון עוקבת: דבר זה מאפשר למעבדים המודרניים בעלי שורות cache ארוכות יעילות רבה. החלק של שורות ה-cache אשר מאפשרים גישה לאיבר הנוכחי במערך תוך שמכיל חלק מהאלמנטים הבאים במערך. ולכך אין מצב שבו ה-cache בקשר CPU <->מסגרות הזיכרון ה"מתבזבז" בכך שאין נעשה בו שימוש.

בניגוד לכך, ביישומים עם רשימות מקושרות:

· יש תוספת למצביעים (והתוספת בדרך כלל עושה שימוש בפונקציות של הקצאת זיכרון כגון (Malloc). דבר זה אומר כי פחות אלמנטים יכולים להתאים לשורת cache בודדת.

· אין ביטחון כי איברים עוקבים ברשימה יהיו עוקבים גם במיקום בזיכרון. דבר זו מוביל בזבוז מסגרות הזיכרון,

בגלל שהכנסה מוקדמת של אלמנטים לתוך ה-cache אינה מתרחשת באופן קבוע..

חזור ל: תוכן עניינים